package seqlist;

/**
 * 基于int的单链表-火车
 * 真正被用户使用的是火车类-单链表对线
 */
public class SingleLinkedList {
    private Node head;
    private int size;

    /**
     * 在链表添加一个新的节点，默认在头部添加
     * @param val
     */
    public void addFirst(int val){
        Node newNode= new Node();
        newNode.val=val;

//        if (head==null){
//            //newNode是第一个节点
//            head=newNode;
//           }
//        else {
//            newNode.next=head;
//            head=newNode;


        if (head!=null){
            newNode.next=head;
        }
        head=newNode;
        size++;
    }

    public void add(int index,int val){
        //若index位置非法
        if (index<0||index>size){
            System.err.println("add index illegal!");
            return;
       }
//        change(index);
        Node newNode=new Node();
        newNode.val=val;
        if (index==0){
            //头插
            addFirst(val);
        }else {
            //索引合法且不是再数组头部插入
            Node prev = head;
            for (int i = 0; i < index-1; i++) {
                prev =prev.next;
            }
            //此时prev一定指向了待插入节点的前驱
            newNode.next=prev.next;
            prev.next=newNode;
            size++;
        }
    }
    public void addLast(int val){
        add(size,val);
    }

    /**
     * 查找第一个值为Val的结点索引是多少
     * @param val
     * @return
     */
    public int getByVakue(int val){
        int index=0;
        for (Node x = head; x!=null; x=x.next) {
            if (x.val==val){
                //第一个值为val的节点
                return index;
            }
            index++;
        }
        //链表种没有值为val的节点
        return -1;
    }

    public boolean contains(int val) {
        int index = getByVakue(val);
//       if (index==-1){
//            return false;
//        }
//        return true;
        return index != -1;
//        return getByVakue(val)!=-1;
    }

    /**
     * 查询索引为index节点的值
     * @param index
     * @return
     */
     public int get(int index){
        if (rangeCheck(index)){
              Node x=head;
            for (int i = 0; i < index; i++) {
                x=x.next;
            }
            return x.val;
        }
         System.err.println("index illegal error");
        return -1;
     }

    /**
     * 修改索引为index位置的节点值为newVal，返回修改前的节点值
     * @param index
     * @param newVal
     * @return
     */
     public int set(int index,int newVal){
         if (rangeCheck(index)){
             Node x=head;
             for (int i = 0; i < index; i++) {
                 x=x.next;
             }
             int oldval = x.val;
             x.val=newVal;
             return oldval;

         }
         System.err.println("index illegal error");
         return -1;
     }

    /**
     * 删除单链表中索引为index位置的节点，返回删除前的节点值
     * @param index
     * @return
     */
     public int remove(int index){
         if (rangeCheck(index)){
             if (index==0){
                 //删除头节点
                 Node x=head;
                 head=head.next;
                 size--;
                 x.next=null;
                 return x.val;
             }else {
                 //找前驱
                 Node prev=head;
                 for (int i = 0; i < index-1; i++) {
                     prev=prev.next;
                 }
                 Node node=prev.next;
                 prev.next=node.next;
                 node.next=null;
                 size--;
                 return node.val;
             }
         }
         System.err.println("remove index illegal");
         return -1;
     }
     public int removeFirst(){
         return remove(0);
     }
     public int removeLast(){
         return remove(size-1);
     }

    /**
     * 删除链表中第一个值为val的节点
     * @param val
     * @return
     */
    public void removeValuOnce(int val) {
        if (head == null) {
            System.err.println("链表为空");
            return;
        }
        if (head.val == val) {
            Node x = head;
            head = head.next;
            x.next = null;
            size--;
        } else {
//需要遍历找到前驱节点，能否知道前节点移动的步数
            Node prev = head;
            while (prev.next != null) {
                //至少还有后继节点
                if (prev.next.val == val) {
                    //此时prev.next为待删除节点；
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                    return;
                }
                    prev = prev.next;
            }
        }
    }

    /**
     * 删除链表中所有值为val的节点
     * @param val
     */
    public void removeAllValue(int val){
        while (head.val == val&&head!=null) {
            Node x=head;
            head = head.next;
            x.next=null;
            size--;
        }

        if (head == null) {
            System.err.println("链表为空");
            return;
        }else {
            Node prev = head;
            while (prev.next != null) {
                //至少还有后继节点
                if (prev.next.val == val) {
                    //此时prev.next为待删除节点；
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                }else {
                    //只有当prev.next.val1=val时候才能向后移动
                    prev = prev.next;
                }
        }
            }
    }

    private boolean rangeCheck(int index) {
        if (index<0||index>size){
            return false;
        }
           return true;
    }

     public String toString(){
        String ret = "";
        Node x = head;
        while (x!=null){
            ret +=x.val;
            ret +="->";
            x=x.next;
        }
    /**
     * for(Node x=head;x!=null;x=x.next;
     * ret+=val;
     * ret+="->"
     */
        ret += "null";
        return ret;
}

}

class Node{
    int val;//每个节点的值
    Node next;//下一个节点的位置
}